1. Field of the Invention
The present invention relates to devices for generating, to any accuracy, the sines or cosines of a sequence of equi-spaced angles. Such sequences are needed in digital signal analysis and in Fourier or Hartley transforms.
2. Description of Related Art
When one performs a harmonic analysis of equi-spaced signals, or of any digital data, one may need sines and cosines of equi-spaced angles, and real or complex combinations of such trigonometric functions. In Fourier transforming one must generate these functions at every "level." It is uneconomical, time-wise, to calculate the sines and cosines from mathematical routines at every step. On the other hand, to provide a full table is uneconomical space-wise.
The on-line creation of exp(i.alpha.), exp(2i.alpha.), exp(3i.alpha.), by successive complex multiplication with exp(i.alpha.) is not "stable": roundoff errors accumulate and an initial error grows exponentially. Similarly, using the sine/cosine addition rules for generating trigonometric functions of successive angles leads to a rapid build-up of errors.
To achieve stability, one must use interpolation, such as in pretabulation by successive halving for the exponential functions:
e.sup.i.alpha. =0.5sec .delta.(e.sup.i(.alpha.+.delta.) +.sup.i(.alpha.-.delta.)), starting with .alpha.=.pi./4 and .delta.=.pi./4 from e.sup.i(.alpha.+.delta.) =i and e.sup.i(.alpha.-.delta.) =1, then creating e.sup.i.pi./8 and e.sup.3i.pi./8, then e.sup.i.pi./16, e.sup.i3.pi./16, e.sup.i5.pi./16, e.sup.i7.pi./16, and so on (where "sec" is an abbreviation of secant). Only a short table of 0.5 sec(.pi./4), 0.5 sec(.pi./8), 0.5 sec(.pi./16), . . . needs to be supplied initially, just long enough to include the half-secant of the spacing of angles in the ultimate table. A full table of the functions of length N=2.sup.n in steps 2.pi./N can be built from n-2 half-secants. This method is used in some simple transform programs (D. Buneman, "Conversion of FFT's to Fast Hartley Transforms," SIAMJ. Sci. Stat. Comp., vol. 7, no. 2, pp. 624-638, 1986), and recommended, because of its stability, in J. Oliver, "Stable methods of evaluating cos (i.pi./n)," J. Inst. Maths. Applic., vol. 16, pp. 247-257, 1975. But it requires memory space for the full table of N entries, because the trigonometric functions are not created in the desired order.